import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Solution {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            String t = in.next();
            //一个饰条也没有
            if(!s.contains(t)){
                System.out.println(0);
                continue;
            }
            int n = s.length();
            int len = t.length();
            int ret = 0;
            int left = 0, right = len-1;
            for(; right < n; right++){
                if(s.substring(left, right+1).contains(t)){
                    ret++;
                    left = right + 1;
                }
            }
            System.out.println(ret);
        }
    }
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        long[] fib = new long[81];
        fib[1] = fib[2] = 1;
        for(int i = 3; i < fib.length; i++){
            fib[i] = fib[i-1] + fib[i-2];
        }
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int from = in.nextInt();
            int to = in.nextInt();
            long ret = 0;
            for(int i = from; i <= to; i++){
                ret += fib[i];
            }
            System.out.println(ret);
        }
    }
    //最长的斐波那契子序列的长度
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        //创建dp表
        int[][] dp = new int[n][n];
        //初始化
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }
        //使用哈希表进行优化
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(arr[0], 0);
        hash.put(arr[1], 1);
        int ret = 0;
        //填表
        for(int i = 2; i < n; i++){
            hash.put(arr[i], i);
            for(int j = 1; j < i; j++){
                int a = arr[i] - arr[j];
                if(a < arr[j] && hash.containsKey(a)){
                    int k = hash.get(a);
                    dp[j][i] = dp[k][j] + 1;
                    ret = Math.max(dp[j][i], ret);
                }
            }
        }
        return ret > 2 ? ret : 0;
    }
    //最长等差数列
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }
        int ret = 2;
        hash.put(nums[0], 0);
        for(int i = 1; i < n; i++){
            for(int j = i+1; j < n; j++){
                int a = 2*nums[i] - nums[j];
                if(hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        Solution solution = new Solution();
        solution.lenLongestFibSubseq(arr);
    }
}